#
# @lc app=leetcode.cn id=115 lang=python3
#
# [115] 不同的子序列
#

# @lc code=start
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        """_summary_

        DP[I][J]  代表s[0:J]中出现t[0-I]的个数
        上三角矩阵
        s[j] == t[i]
        dp[i-1][j-1] + 之前{上一次}s[j`] == t[i]时的dp[i-1][j`-1]

        Args:
            s (str): _description_
            t (str): _description_

        Returns:
            int: _description_
        """
        m = len(t)
        n = len(s)
        dp = [[0 for i in range(n)] for j in range(m)]
        if t[0] == s[0]:
            dp[0][0] = 1
        
        # dp[0][0] = 0
        res = dp[0][0]
        for i in range(1, n, 1):
            if t[0] == s[i]:
                res += 1
                dp[0][i] = res
            else:
                dp[0][i] = dp[0][i-1]
        
        for i in range(1, m, 1):
            res = 0
            for j in range(i, n, 1):
                if t[i] == s[j]:
                    res += dp[i-1][j-1]
                    dp[i][j] = res
                else:
                    dp[i][j] = dp[i][j-1]
        
        # print(dp)
        return dp[m-1][n-1]
# @lc code=end

